package com.zj.leetcode.medium.dynamicProgramming;

/**
 * @program: algorithm
 * @description: 目标和
 * 494 target-sum
 * @author: Zhang Bo
 * @create: 2022-05-17 21:18:57
 **/
public class TargetSum {
    public static void main(String[] args) {
        Solution solution = new TargetSum().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findTargetSumWays(int[] nums, int target) {
            int len = nums.length;
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if ((sum + target) % 2 == 1 || Math.abs(target) > sum) return 0;
            int pos = (sum + target) / 2;
            int[] dp = new int[pos + 1];
            dp[0] = 1;
            for (int num : nums) {
                for (int j = pos; j >= num; j--) {
                    dp[j] += dp[j - num];
                }
            }
            return dp[pos];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}